#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <assert.h>
#include <cstdlib>
#include <fstream>

const int TESTS = 100;

size_t minIndex (size_t a, size_t b, size_t c){
    if (a <= std::min(b,c))
        return 1;
    if (b <= std::min(a,c))
        return 2;
    return 3;
}

size_t min(size_t a, size_t b, size_t c){
    return std::min(a, std::min( b, c));
}

std::string Vagner(std::string &iData, std::string &jData){
    
    std::vector<std::vector<size_t>> table(iData.length()+1);
    
    for (size_t i = 0; i < iData.length()+1; ++i){
        table[i].resize(jData.length()+1);
        table[i][0] = i;
    }
    for (size_t j = 0; j < jData.length()+1; ++j)
        table[0][j] = j;
    
    
    for (size_t i = 1; i <= iData.length(); ++i){
        for (size_t j = 1; j <= jData.length(); ++j){
            if (iData[i-1] == jData[j-1]){
                table[i][j] = table[i-1][j-1];
            }else{
                table[i][j] = 1 + min(table[i][j-1],//i
                                      table[i-1][j],//d
                                      table[i-1][j-1]);//r
            }
        }
    }
    
    std::string edit;
    size_t i = iData.length(), j = jData.length();
    
    // получение последовательности редактирований
    while (i*i + j*j != 0){
        if (!i){
            j--;
            edit.push_back('I');
            continue;
        }
        if (!j){
            i--;
            edit.push_back('D');
            continue;
        }
        size_t minInd = minIndex(table[i-1][j-1],
                                 table[i-1][j],
                                 table[i][j-1]);
        if (minInd == 1){
            if (iData[i-1]==jData[j-1])
                edit.push_back('N');
            else
                edit.push_back('R');
            i--;
            j--;
            continue;
        }
        if (minInd == 2){
            edit.push_back('D');
            i--;
            continue;
        }
        edit.push_back('I');
        j--;
    }
    reverse(edit.begin(), edit.end());
    return edit;
}

// [begin; end)
std::vector<size_t> countLR(std::string &iData,
                            std::string &jData,
                            bool way,// 0-backwards, 1-normal
                            size_t iBegin,
                            size_t iEnd,
                            size_t jBegin,
                            size_t jEnd)
{
    size_t leftSize = iEnd - iBegin, rightSize = jEnd - jBegin;
    std::vector<std::vector<size_t>> LR(2);
    LR[0].resize(rightSize + 1);
    LR[1].resize(rightSize + 1);
    
    for (size_t i = 0; i < rightSize + 1; ++i){
        LR[0][i] = i;
    }
    
    size_t columnCounter = 1, columnIndex = 1, iDataBackwards = 0, jDataBackwards = 0;
    
    // корректирование длин для разворота строк
    if(!way){
        iDataBackwards = leftSize;
        jDataBackwards = rightSize;
    }
    
    while(columnCounter < leftSize + 1){
        LR[columnIndex][0] = columnCounter;
        for (int i = 1; i < rightSize + 1; ++i){
            if (way){
                iDataBackwards = 2*columnCounter - 1;
                jDataBackwards = 2*i - 1;
            }
            bool shift = 1;
            if(iData[iDataBackwards-columnCounter+iBegin] == jData[jDataBackwards-i+jBegin])
                shift = 0;
            LR[columnIndex][i] = min(LR[columnIndex][i-1] + 1,
                                     LR[(columnIndex + 1) % 2][i] + 1,
                                     shift + LR[(columnIndex + 1) % 2][i-1]);
        }
        ++columnCounter;
        ++columnIndex;
        columnIndex %= 2;
    }
    ++columnIndex;
    columnIndex %= 2;
    return LR[columnIndex];
}

// [begin; end)

std::string Hirschberg(std::string &iData,
                    std::string &jData,
                    size_t iBegin,
                    size_t iEnd,
                    size_t jBegin,
                    size_t jEnd)
{
    // таблица из 1 столбца -> рекурсия не нужна
    if (iEnd - iBegin != 1 && jEnd - jBegin != 1){
        size_t midPart = iBegin + (iEnd - iBegin)/2 - 1;
        std::vector<size_t> leftPart = countLR(iData, jData, 1, iBegin, midPart + 1, jBegin, jEnd);
        std::vector<size_t> rightPart = countLR(iData, jData, 0, midPart + 1, iEnd, jBegin, jEnd);
        
        size_t index = 0;
        for (size_t i = 0; i < leftPart.size(); ++i){
            if (leftPart[i] + rightPart[leftPart.size()-1-i] < leftPart[index] + rightPart[leftPart.size()-1-index])
                index = i;
        }

        std::string firstHalf = Hirschberg(iData, jData, iBegin, midPart + 1, jBegin, jBegin + index);
        std::string secondHalf = Hirschberg(iData, jData, midPart + 1, iEnd, jBegin + index, jEnd);

        return firstHalf+secondHalf;
    }

    // обрезание строк для Вагнера
    std::string iDataCut = "", jDataCut = "";
    iDataCut.insert(iDataCut.begin(), iData.begin() + iBegin, iData.begin() + iEnd);
    jDataCut.insert(jDataCut.begin(), jData.begin() + jBegin, jData.begin() + jEnd);

    return Vagner(iDataCut, jDataCut);
}

std::string Hirschberg(std::string &iData, std::string &jData){
    if (iData.length() == 0 && jData.length() == 0)
        return "";
    return Hirschberg(iData, jData, 0, iData.length(), 0, jData.length());
}

std::string generateRandom (size_t n){
    std::string result;
    for (size_t i = 0; i < n; ++i){
        result.push_back(char('a' + (rand()%20)));
    }
    return result;
}

size_t countDist (std::string &edit){
    int dist = 0;
    for (size_t i = 0; i < edit.length(); ++i){
        if (edit[i]!='N')
            dist++;
    }
    return dist;
}

bool correctness(std::string &edit, std::string &iData, std::string &jData){
    std::string scomp;
    size_t jIt = 0, iIt = 0;
    for (size_t testIt = 0; testIt < edit.length(); ++testIt){

        if (edit[testIt] == 'R'){
            scomp.push_back(jData[jIt]);
            jIt++;
            iIt++;
        }
        if (edit[testIt] == 'I'){
            scomp.push_back(jData[jIt]);
            jIt++;
        }
        if (edit[testIt] == 'N'){
            scomp.push_back(iData[iIt]);
            jIt++;
            iIt++;
        }
        if (edit[testIt] == 'D'){
            iIt++;
        }
    }
    
    if (scomp == jData)
        return true;
    
    return false;
}

void runTests(){
    std::string iData, jData;
    
    bool correct = true;
    for (size_t testCounter = 0; testCounter < TESTS; ++testCounter){
        iData = generateRandom(rand()%100 + 1);
        jData = generateRandom(rand()%100 + 1);
        
        // HIRSCHBERG
        auto hirAns = Hirschberg(iData, jData);
        size_t hirDist = countDist(hirAns);
        //std::cout << "\nHirs\n" << hirAns << "\n" << hirDist;
        
        // VAGNER
        auto vagAns = Vagner(iData, jData);
        size_t vagDist = countDist(vagAns);
        //std::cout << "\n\nVagner\n" << vagAns << "\n" << vagDist << "\n";
        
        correct = correctness(hirAns, iData, jData);
        if (vagDist != hirDist)
            correct = false;
        if (!correct){
            std::cout << "ERROR\n";
            break;
        }
    }
    if (correct)
        std::cout << "TESTS OK\n";
}

void outResult (std::string &edit, std::string &iData, std::string &jData){
    size_t iIt = 0, jIt = 0;
    for (size_t testIt = 0; testIt < edit.length(); ++testIt){
        if (edit[testIt] == 'R'){
            std::cout << "\nposition " << iIt << ": replace '" << iData[iIt] << "' -> '" << jData[jIt] << "'";
            iIt++;
            jIt++;
        }
        if (edit[testIt] == 'I'){
            std::cout << "\nposition " << iIt << ": insert '" << jData[jIt] << "'";
            jIt++;
        }
        if (edit[testIt] == 'D'){
            std::cout << "\nposition " << iIt << ": delete '" << iData[iIt] << "'";
            iIt++;
        }
        if (edit[testIt] == 'N'){
            iIt++;
            jIt++;
        }
    }
}

int main(){
    
    runTests();
    
    std::ifstream inFirst, inSecond;
    inFirst.open("inputFirst.txt");
    std::string inputFirst((std::istreambuf_iterator<char>(inFirst)), std::istreambuf_iterator<char>());
    inFirst.close();
    
    inSecond.open("inputSecond.txt");
    std::string inputSecond((std::istreambuf_iterator<char>(inSecond)), std::istreambuf_iterator<char>());
    inSecond.close();
    
    auto edit = Hirschberg(inputFirst, inputSecond);
    size_t dist = countDist(edit);
    outResult(edit, inputFirst, inputSecond);
    std::cout << "\nDISTANCE: " << dist;
    
    return 0;
}